#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-10-23 8:46 上午
# @Author  : yangdy
# @File    : 2020-10-23.234.回文链表
# @Software: PyCharmCE
from tools.my_methods import *


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def __init__(self):
        self.p = None

    def isPalindrome(self, head: ListNode) -> bool:

        def dfs(rt):
            if not rt:
                self.p = head
                return True

            if not dfs(rt.next):
                return False
            if rt.val == self.p.val:
                self.p = self.p.next
                return True
            return False

        return dfs(head)
